public class PiramidSort {

	public static void main(String[] args) {

		int[] mas = { 13, 15, 10, 12, 30, 11, 5, 25, 5, 5, 1, 1, 1, 1, 1, 5, 6,
				7, 8, 13, 3, 3, 3, 4, 5, 2, 1, 2, 1, 2, 1 };

		for (int i = 0; i < mas.length; i++) {
			System.out.print(mas[i] + ",");
		}
		System.out.println();
		mas = sort(mas);
		for (int i = 0; i < mas.length; i++) {
			System.out.print(mas[i] + ",");
		}
	}

	public static int[] sort(int[] mas) {

		mas = buildPiramida(mas);
		mas = completeSort(mas);
		return mas;
	}

	static int[] completeSort(int[] mas) {

		int len = mas.length;
		for (int i = len - 1; i > 0; i--) {
			mas = obmen(mas, 0, i);
			mas = proseiatEl(mas, i, 0);
		}
		return mas;
	}

	static int[] buildPiramida(int[] mas) {

		int len = mas.length;
		for (int i = len - 1; i >= 0; i--) {
			mas = proseiatEl(mas, len, i);
		}
		return mas;
	}

	static int[] proseiatEl(int[] mas, int len, int i) {

		int maxSonValInd = maxSonValInd(mas, len, i);
		if (maxSonValInd == -1) {
			return mas;
		} else {
			int valPar = mas[i];
			int maxSonVal = mas[maxSonValInd];
			if (valPar < maxSonVal) {
				mas = obmen(mas, i, maxSonValInd);
				mas = proseiatEl(mas, len, maxSonValInd);
			}
		}
		return mas;
	}

	static int maxSonValInd(int[] mas, int len, int parentIndex) {

		int leftSonInd = 2 * parentIndex + 1;
		if (leftSonInd > len - 1) {
			return -1;
		}
		int rightSonInd = 2 * parentIndex + 2;
		if (rightSonInd > len - 1) {
			return leftSonInd;
		}

		int leftSonVal = mas[leftSonInd];
		int rightSonVal = mas[rightSonInd];
		if (leftSonVal > rightSonVal) {
			return leftSonInd;
		}
		return rightSonInd;
	}

	static int[] obmen(int[] mas, int ind0, int ind1) {

		int value0 = mas[ind0];
		int value1 = mas[ind1];
		mas[ind0] = value1;
		mas[ind1] = value0;
		return mas;
	}
}
